home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 90 / CD Actual 90.iso / Software3D / PovLab / povlab / PLUGINS / RS_IFS.ZIP / IFS_INFO.GER < prev    next >
Encoding:
Text File  |  1996-03-14  |  8.1 KB  |  173 lines
  1. Robert Seidel
  2. seidel@ifk.uni-jena.de
  3.  
  4. Iterated Function Systems (kurz IFS)
  5.  
  6.  
  7. Viel Computernutzer denken bei dem Wort Fraktale an die berühmte
  8. Mandelbrotmenge, es gibt aber jedoch weitaus mehr Fraktalsorten
  9. und eine ganz besondere sind die Iterated Function Systems.
  10. Diese "iterierten Funktionssysteme" wurden von Michael Barnsley
  11. und seinen Kollegen entdeckt und haben einen weitaus größeren
  12. Nutzen für die heutigen Computer als viele andere Fraktalsorten.
  13.  
  14. Diese ermöglichen nämlich eine der effektivsten Bild-
  15. komprimierungen, die selbst dem vielgelobten JPEG-Format an
  16. Qualität und Komprimierungsfaktor weit überlegen sind. So ist es
  17. zum Beispiel möglich einen Farn (FARN.IFS) mit nur sehr wenigen
  18. Werten (28 Werte x 4 Byte (SINGLE-Zahlen) = 112 Byte) zu
  19. beschreiben. Mit Hilfe eines Entpackers kann man aber ein
  20. SuperVGA-Bild (z.B. 800x600x256) erhalten, welches unkomprimiert
  21. fast ein halbes Megabyte Platz einnehmen würde. 
  22. Der Komprimierungsfaktor beträgt dabei über 4200 zu 1! Wäre man
  23. in der Lage alle Daten so zu komprimieren, würde eine einzige
  24. HD-Diskette für die meisten Anwender ausreichen, man hätte dann
  25. 6 Gigabyte zur Verfügung!
  26.  
  27. Dieses Programm kann leider nur fertige Werte entpacken, Michael
  28. Barnsley hat aber Wege gefunden jedes beliebige Bild so zu
  29. Komprimieren (sogar bis 10000 zu 1) und besitzt auch eine eigene
  30. Firma "Iterated Systems", die solche Programme und
  31. Programmiertools anbietet (siehe auch DOS International 7/95
  32. Seite 114/115). Dieses Verfahren scheint so gut zu sein, daß es
  33. inzwischen auch von anderen Herstellern genutzt wird, so z.B. in
  34. MS Encarta.
  35.  
  36. Den Kern des Programmes stellt dabei die affine Abbildung
  37.  
  38.      │ x' │   │ a b ││ x │   │ e │
  39.      │    │ = │     ││   │ + │   │
  40.      │ y' │   │ c d ││ y │   │ f │
  41.  
  42. dar. Diese läßt sich aber einfacher darstellen, und sie wird
  43. damit für uns und den Computer besser verständlich:
  44.  
  45.        x = a * xalt + b * yalt + e
  46.        y = c * xalt + d * yalt + f  
  47.  
  48. Aus dieser Form wird ersichtlich, daß x und y die Koordinaten
  49. eines Punktes beschreiben. Diese berechnen sich aus den
  50. Koordinaten des alten Punktes (xalt/yalt) und den Werten von a,
  51. b, c, d, e und f. Die Werte von a, b, c und d sind für die
  52. Drehung (α) und die Schrumpfung/Vergrößerung (r) der alten
  53. Koordinaten verantwortlich, während die Variablen e und f eine
  54. Verschiebung gegenüber dem alten Punkt bewirken. a, b, c, und d
  55. können dann wie folgt berechnet werden:
  56.  
  57.       │ a b │       │ cos α -sin α │
  58.       │     │ = r * │              │
  59.       │ c d │       │ sin α  cos α │
  60.  
  61. Dies hört sich alles sehr kompliziert an, wenn man sich aber die
  62. Werte des Sierpinski-Dreiecks (SIER.IFS) genauer anschaut,
  63. erkennt man deren Bedeutung wesentlich schneller, während der
  64. Farn(FARN.IFS) etwas zu komplex dafür ist. Bei dem Dreieck
  65. erkennt man deutlich, daß jede Seite gegenüber der vorherigen um
  66. die Hälfte (0.5) verkleinert wurde. Ebenso erkennbar ist, daß
  67. die Verschiebungen ein Dreieck bilden.
  68. Neben diesen Werten, die das Bild beschreiben, taucht auch noch
  69. ein Wert p auf. Dieser stellt die Wahrscheinlichkeit (zwischen
  70. 0 und 1) dar, welche affine Abbildung wie oft genutzt wird. So
  71. beschreiben zum Beispiel die 4 affinen Abbildungen  verschiedene
  72. Teile (Blätter, Sproßachse, ...) des Farns. Die Wahr-
  73. scheinlichkeit gibt dabei die "Wichtigkeit" der einzelnen Teile
  74. an, so haben die Blätter eine sehr hohe Wahrscheinlichkeit
  75. (0.85) und werden entsprechend schneller dargestellt. Würde man
  76. alle p auf 0.25 setzen, also alle Teile gleichwertig behandeln,
  77. würde das Farnbild erst nach sehr langer Zeit wie gewünscht
  78. aussehen.
  79.  
  80. (Tabellenform :
  81.   Kopf :    a   b   c   d   e   f   p
  82.   Werte:    ... )
  83.  
  84. Wer sich noch etwas genauer mit dem mathematischen Hintergrund
  85. beschäftigen möchte, dem seien die Bücher "Fraktale Geometrie
  86. von E.D. Schmitter", "Algorithmen für Chaos und Fraktale" von
  87. Dietmar Herrman und der Artikel des "PC Magazine" vom 8.
  88. November 1994 empfohlen. Das Freeware-Programm "FRACTINT" bietet
  89. ebenfalls noch mehr IFS-Werte, die sehr einfach übernommen
  90. werden können. Die Datei "FRACTINT.IFS" enthält verschiedene
  91. Werte, die durch Kommas in einem Editor getrennt werden müssen.
  92. Weiter müssen noch einige kleine Änderungen vorgenommen werden,
  93. dazu später eine genaue Beschreibung des IFS-Formates.
  94. Es lohnt sich im übrigen für jeden, der sich ein wenig für
  95. Fraktale interessiert "FRACTINT" genauer anzuschauen, zumal es
  96. kostenlos ist!
  97.  
  98. Zum Programm:
  99.  
  100. Das Programm IFS.BAS wurde für QBASIC geschrieben, ist aber auch
  101. ohne Änderungen unter PowerBASIC einsetzbar. Da PowerBASIC ein
  102. Compiler ist, erfolgt auch die Darstellung entsprechend
  103. schneller:
  104.  
  105.  Benchmark:  Bild: "FARN.IFS" mit 32750 Punkten
  106.  
  107.              Rechner:     Zeit in Sekunden:             Faktor:
  108.                           QBASIC    PowerBASIC 3.00c
  109.              486 SX 25     64.35    19.17                3.36
  110.              386 DX 16    205.15     9.55               21.48
  111.  
  112. Dies zeigt nicht nur die Vorteile eines Compilers, sondern auch
  113. die eines Coprozessors bei mathematischen Berechnungen!
  114.  
  115. Als Standard-Datentyp werden einfach genaue Zahlen (SINGLE)
  116. verwendet, die Schleifenzähler und einige andere Variablen sind
  117. aus Geschwindigkeitsgründen INTEGER-Zahlen (dies ist für unsere
  118. PASCAL/C-Freunde wichtig). Das Programm hat die IFS-Tabelle
  119. nicht fest integriert und ist somit wesentlich flexibler. Es
  120. greift auf Dateien mit der Endung "IFS" zu, diese sind wie folgt
  121. aufgebaut:
  122.  
  123.   Zeile:    Beschreibung:
  124.   1.        Name des IFS-Bildes (bei abstrakten Gebilden recht 
  125.             nützlich)
  126.   2.        Anzahl(n) der affinen Abbildungen (nur durch       
  127.             Arrayspeicher begrenzt)
  128.   3. - n.   Werte der affinen Abbildung durch Komma getrennt
  129.             (a, b, c, d, e, f, p)
  130.   (n+1).    WINDOW-Koordinaten
  131.  
  132. Die WINDOW-Koordinaten müssen für neue IFS-Bilder abgestimmt
  133. werden, somit wird aber die beste Wiedergabe erreicht. (Man kann
  134. die WINDOW-Werte auch berechnen lassen, dies wäre aber etwas zu
  135. komplex für dieses Programm.)
  136. 17 Tabellen mit IFS-Werten (für z.B. Farne, Bäume, Blätter,
  137. Cluster, Drachen, Sierpinski-Dreiecke und Teppiche und einige
  138. mehr) sind hier abgedruckt (siehe IFS-Dateien auf Diskette),
  139. dies sollte für den Anfang genügen. In den erwähnten Quellen
  140. finden sich aber noch weitere interessante Werte die durch
  141. dieses Dateiformat leicht vom Leser für das Programm zugänglich
  142. gemacht werden können. Man kann aber auch eigene Werte nutzen
  143. oder mit den gegebenen experimentieren.
  144. Eine Datei kann bei Programmstart ausgewählt werden, in
  145. PowerBASIC/QuickBASIC ist es auch möglich den Namen als
  146. Kommandozeilenparameter zu übergeben, da hier der Befehl
  147. "COMMAND$" zur Verfügung steht (im Listing IFS.BAS nur "'"
  148. entfernen). Zu beachten ist dabei nur, daß die Endung "IFS"
  149. nicht angegeben werden darf.
  150. Nachdem nun alle Werte eingelesen wurden, beginnt das Programm
  151. ein Bild zu berechnen und zu anzuzeigen. Dabei arbeitet es
  152. solange, bis der Nutzer eine Taste drückt. Da das Warten nach
  153. jedem gesetzten Punkt recht lange dauert, wird eigentlich nur
  154. alle 1000 Punkte überprüft, ob eine Taste gedrückt wurde. Dies
  155. geschieht in einer Schleife mit dem Zähler "speed" und bringt
  156. selbst auf schnellen Rechnern deutliche Geschwindigkeits-
  157. vorteile. Man sollte schon eine Weile auf das Bild warten, meist
  158. werden dann erst alle Details erkennbar. Zum Beispiel sehen die
  159. Sierpinski-Figuren (Teppich und Dreieck) erst nach längerem
  160. ungestörten Rechnen perfekt aus.
  161. Vor der Zeile "PSET(x, y), col" kann man der Farbvariablen "col"
  162. einen Wert zuweisen. Dieser kann konstant (beim Farn z.B. grün),
  163. zufällig oder nach einer eigenen Formel bestimmt sein. Mit guten
  164. Formeln, einer SVGA-Auflösung und einer guten Palette sind die
  165. Bilder sicherlich kaum vom natürlichen Original zu unter-
  166. scheiden. (Ich besitze leider nur einen SW-Bildschirm, so bleibt
  167. mir dieser Farbgenuß leider verwehrt.) Da der Quellcode leicht
  168. verständlich ist, auch wenn die mathematische Seite nicht 100
  169. prozentig durchschaut wurde, bietet sich die Implementierung von
  170. neuen Features (SVGA-Darstellung, kleines Menüsystem, Assembler-
  171. algorithmen, Bildkomprimierung (?!?)) geradezu an. Viel Spass
  172. beim Tüfteln! 
  173.